package test.shortestpath;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * Implement the shortest path algorithm as http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
 * Note that we can't do BFS (breadth-first-search) to navigate the graph here, this is well discussed 
 * in http://www.cs.cornell.edu/courses/cs312/2002sp/lectures/lec20/lec20.htm
 * 
 * @author ginger
 * 
 */
public class DijkstraShortestPath {

	public List<Vertex> findShortestPath(Graph graph, Vertex startNode, Vertex targetNode) {
		// Use PriorityQueue rather than FIFO queue to retrieve the node with minimum distance !!!
		PriorityQueue<Vertex> queue = new PriorityQueue<Vertex>(graph.getVertices().size(), new Comparator<Vertex>() {
			@Override
			public int compare(Vertex v1, Vertex v2) {
				return v1.getDistance() - v2.getDistance();
			}
		});

		// initialize
		for (Vertex node : graph.getVertices()) {
			node.setDistance(Integer.MAX_VALUE);
			node.setPrevous(null);
			queue.add(node);
		}

		queue.add(startNode); // seed, bread-first search
		startNode.setDistance(0);

		while (!queue.isEmpty()) {
			Vertex current = queue.poll();
		
			System.out.println("Current is " + current.getId() + " Queue size " + queue.size());
			
			if (current.getDistance() == Integer.MAX_VALUE) {
				return null;
			}

			for (Map.Entry<Vertex, Edge> entry : current.getNeighbors().entrySet()) {
				Vertex node = entry.getKey();
				if (node.getDistance() > current.getDistance() + entry.getValue().getWeight()) {
					node.setDistance(current.getDistance() + entry.getValue().getWeight());
					node.setPrevous(current);
				}
			}
		}

		// print path
		List<Vertex> path = new LinkedList<Vertex>();
		path.add(targetNode);
		Vertex node = targetNode;
		while (node.getPrevous() != null) {
			path.add(0, node.getPrevous());
			node = node.getPrevous();
		}

		return path;
	}

	public Graph constructGraph() {
		List<Vertex> vertices = new ArrayList<Vertex>();
		for (int i = 1; i <= 6; i++) {
			vertices.add(new Vertex(i));
		}
		
		Graph g = new Graph(vertices, new ArrayList<Edge>());
		g.addEdge(new Edge(14, vertices.get(0), vertices.get(5)));
		g.addEdge(new Edge(9, vertices.get(0), vertices.get(2)));
		g.addEdge(new Edge(7, vertices.get(0), vertices.get(1)));
		g.addEdge(new Edge(10, vertices.get(1), vertices.get(2)));
		g.addEdge(new Edge(15, vertices.get(1), vertices.get(3)));
		g.addEdge(new Edge(2, vertices.get(2), vertices.get(5)));
		g.addEdge(new Edge(11, vertices.get(2), vertices.get(3)));
		g.addEdge(new Edge(6, vertices.get(3), vertices.get(4)));
		g.addEdge(new Edge(9, vertices.get(4), vertices.get(5)));
		return g;
	}

	public static void main(String[] args) {
		DijkstraShortestPath alg = new DijkstraShortestPath();
		Graph g = alg.constructGraph();
		List<Vertex> path = alg.findShortestPath(g, g.getVertex(1), g.getVertex(5));
		boolean first = true;
		for (Vertex v : path) {
			if (!first) {
				System.out.print(" -> ");
			}
			
			System.out.print(v.getId() + "(" + v.getDistance() + ")");
			first = false;
		}

	}
}
